1. Field of the Invention
This invention relates to the field of data processing systems. More particularly, this invention relates to data processing systems for calculating Fast Fourier Transform of two or more dimensions.
2. Description of the Prior Art
The computation of Fast Fourier Transforms is a data processing requirement in many application areas. Multi-dimensional Fast Fourier Transforms are often employed in areas such as image processing. The computational overhead associated with the calculation of Fast Fourier Transforms is significant and accordingly measures which can be taken to improve the speed of Fast Fourier Transforms are advantageous. It is known to provide special purpose hardware for computing Fast Fourier Transforms, such as within digital signal processing integrated circuits. Such special purpose hardware still requires controlling and configuring for the particular computation to be performed. As the hardware becomes more specialised, the control complexity increases accordingly. This leads either to a fixed hardwired controller, which limits the applicability of the hardware specifically to “that” FFT, or to an increase in program size on a “shared resource architecture” which is not limited to the computations of only “that” FFT. Furthermore, computational cycles consumed configuring such special purpose hardware and resetting it between processing loops is a processing overhead which it is advantageous to reduce.
When computing a multi-dimensional Fast Fourier Transform in accordance with known techniques, it is known to separately compute the Fast Fourier Transform components in each dimension in sequence in order to eventually build up the multi-dimensional result. Thus, in the case of a two-dimensional Fast Fourier Transform, it would be normal to first compute all of the one-dimensional row Fast Fourier Transform results followed by all of the one-dimensional column Fast Fourier Transform results. In such a system, whilst the inner loop of the code may be implemented efficiently using either special purpose hardware (e.g. a pipeline for the FFT “butterfly”), or in the software case handcrafted/optimised code, the outer loops needed to cycle among the rows and columns consume disadvantageous additional code size overhead as well as processing cycles.